package com.mojito.learn.algorithm.datastructure;

import java.util.*;
import java.util.stream.Collectors;

import static com.mojito.common.constant.SymbolConsts.*;

/**
 * 二叉树
 *
 * @author liufengqiang
 * @date 2021-02-28 00:09:34
 */
public class TreeNode {

    public int val;
    public TreeNode left;
    public TreeNode right;

    public TreeNode(int val) {
        this.val = val;
    }

    public static TreeNode build(String val) {
        return build(val, COMMA);
    }

    public static TreeNode build(String val, String split) {
        if (val.startsWith(LEFT_PARENTHESIS)) {
            val = val.substring(1, val.length() - 1);
        }

        List<Integer> vals = Arrays.stream(val.split(split))
                .map(o -> "null".equals(o.trim()) ? null : Integer.parseInt(o.trim())).collect(Collectors.toList());
        List<TreeNode> nodeList = new LinkedList<>();
        vals.forEach(o -> nodeList.add(o == null ? null : new TreeNode(o)));

        // 对前lastParentIndex-1个父节点按照父节点与孩子节点的数字关系建立二叉树
        for (int parentIndex = 0; parentIndex < vals.size() / 2 - 1; parentIndex++) {
            // 左孩子
            nodeList.get(parentIndex).left = nodeList.get(parentIndex * 2 + 1);
            // 右孩子
            nodeList.get(parentIndex).right = nodeList.get(parentIndex * 2 + 2);
        }
        // 最后一个父节点:因为最后一个父节点可能没有右孩子，所以单独拿出来处理
        int lastParentIndex = vals.size() / 2 - 1;
        // 左孩子
        if (nodeList.get(lastParentIndex) != null) {
            nodeList.get(lastParentIndex).left = nodeList.get(lastParentIndex * 2 + 1);
        }
        // 右孩子,如果数组的长度为奇数才建立右孩子
        if (vals.size() % 2 == 1) {
            nodeList.get(lastParentIndex).right = nodeList.get(lastParentIndex * 2 + 2);
        }
        return nodeList.get(0);
    }

    @Override
    public String toString() {
        if (this.left == null || this.right == null) {
            return LEFT_PARENTHESIS + this.val + RIGHT_PARENTHESIS;
        }

        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(this);
        StringBuilder stringBuilder = new StringBuilder(LEFT_PARENTHESIS);

        while (!queue.isEmpty()) {
            int queueSize = queue.size();
            for (int i = 0; i < queueSize; i++) {
                TreeNode node = queue.poll();
                stringBuilder.append(node.val).append(COMMA);
                if (node.left != null) {
                    queue.offer(node.left);
                }
                if (node.right != null) {
                    queue.offer(node.right);
                }
            }
        }
        return stringBuilder.substring(0, stringBuilder.length() - 1) + RIGHT_PARENTHESIS;
    }

    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (o == null || getClass() != o.getClass()) return false;
        TreeNode treeNode = (TreeNode) o;
        return val == treeNode.val &&
                Objects.equals(left, treeNode.left) &&
                Objects.equals(right, treeNode.right);
    }

    @Override
    public int hashCode() {
        return Objects.hash(val, left, right);
    }
}
